#include <stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

// 反转 head 链表，然后返回反转后的新的头节点
struct ListNode* reverseList(struct ListNode *head) {
    // 最小子问题
    if (head == NULL || head->next == NULL) return head;
    struct ListNode *ret = reverseList(head->next);
    // 反转两个节点
    head->next->next = head;
    head->next = NULL;

    return ret;
}

// 递归
void printList(struct ListNode *head) {
    if (head == NULL) return;
    printf("%d\n", head->val);
    printList(head->next);
}

int main(void) {
    struct ListNode node2 = {3, NULL};
    struct ListNode node1 = {2, &node2};
    struct ListNode head = {1, &node1};
    printList(reverseList(&head));
    return 0;
}
